#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2019 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""

"""

DEFAULT_VALUE = 0


class PerfectSquare:
    def __init__(self, square_pix, available_edges):
        self.square_pix = square_pix
        self.available_edges = sorted(available_edges)
        self.edge_len = len(square_pix)

        self.visible = [0] * len(available_edges)

        # print("edges: ", self.available_edges)
        # print("edge_len: ", self.edge_len)
        # print("square: ", self.square_pix)

        self.calc()

    def calc(self, ):
        ok = self.dfs_fill_row_col(0, 0)
        if ok:
            print("this is great!")
            # last_row_edges = set(self.square_pix[self.edge_len - 1])
            last_row_edges = self.square_pix[self.edge_len - 1]
            print("last row is: ", last_row_edges)
            print("unique last row is: ", set(last_row_edges))
        else:
            print("no solution for this!")

    def dfs_fill_row_col(self, row, col):
        assert row < self.edge_len
        assert col <= self.edge_len

        if row == self.edge_len-1 and col == self.edge_len:
            # greate trigger, gave over!
            print("game over trigger! great search.")
            return True

        if col == self.edge_len:
            row += 1
            col = 0

        # 都填满了, over
        row, col = self.find_first_empty_pix(row, col)
        if row == -1 and col == -1:
            return True
        # print(row, col)

        # 因为是find_first_empty_pix执行的, 所以empty_block_len 一定 >= 1
        empty_block_len = self.find_empty_block_len(row, col)
        assert empty_block_len >= 1
        # print("empty_block_len: ", empty_block_len)


        # 截枝法
        for idx, fill_edge in enumerate(self.available_edges):
            if self.visible[idx]:
                continue

            # 既可以这样判断, 也可以用can_fill()判断, 效果一致
            if fill_edge > empty_block_len:
                return False

            # if not self.can_fill(row, col, fill_edge):
            #     return False

            self.visible[idx] = 1
            set_block(self.square_pix, row, col, fill_edge)

            ok = self.dfs_fill_row_col(row, col+fill_edge)
            if ok:
                # 找到了
                print("set (%s, %s) %s" % (row, col, fill_edge))
                return True

            # print("(%s %s) %s failed" % (row, col, fill_edge))
            self.visible[idx] = 0
            clear_block(self.square_pix, row, col, fill_edge)

        return False

    def find_empty_block_len(self, row, col):
        c_len = 0
        r_len = 0

        for c in range(col, self.edge_len):
            if self.square_pix[row][c] == 0:
                c_len += 1
            else:
                # NOTE: 之前这里没有break, 所以出错
                # FIXED
                break

        for r in range(row, self.edge_len):
            if self.square_pix[r][col] == 0:
                r_len += 1
            else:
                # NOTE: 之前这里没有break, 所以出错
                # FIXED
                break

        return min(r_len, c_len)

    def find_first_empty_pix(self, row, col):
        for c in range(col, self.edge_len):
            if self.square_pix[row][c] == 0:
                return row, c

        for r in range(row+1, self.edge_len):
            for c in range(self.edge_len):
                if self.square_pix[r][c] == 0:
                    return r, c

        return -1, -1

    def can_fill(self, row, col, fill_edge):
        if row + fill_edge > self.edge_len:
            return False

        if col + fill_edge > self.edge_len:
            return False

        for r in range(row, row+fill_edge):
            for c in range(col, col+fill_edge):
                if self.square_pix[r][c] != 0:
                    return False

        return True


def make_mat(rows, cols, init_v=0):
    one_row = [init_v] * cols
    matrix = [list(one_row) for i in range(rows)]
    return matrix

def set_block(square, left_up_row, left_up_col, edge, value=DEFAULT_VALUE):
    left_up_row, left_up_col = left_up_row, left_up_col
    right_down_row, right_down_col = left_up_row+edge, left_up_col + edge

    if value == DEFAULT_VALUE:
        set_value = edge
    else:
        set_value = value

    set_block_mat(square, (left_up_row, left_up_col), (right_down_row, right_down_col), set_value)

def clear_block(square, left_up_row, left_up_col, edge):
    left_up_row, left_up_col = left_up_row, left_up_col
    right_down_row, right_down_col = left_up_row+edge, left_up_col + edge

    set_block_mat(square, (left_up_row, left_up_col), (right_down_row, right_down_col), 0)

def set_block_mat(square, left_up, right_down, value=1):
    # 把一块block值初始化为value
    # [left_up, right_down), 不包括右边
    left_up_row, left_up_col = left_up
    right_down_row, right_down_col = right_down

    for row in range(left_up_row, right_down_row):
        for col in range(left_up_col, right_down_col):
            square[row][col] = value


def main():
    print("start main")

    # edge_len = 10
    # square_pix = make_mat(edge_len, edge_len, 0)
    # s1 = 3
    # s2 = 4
    # s3 = 2
    # set_block_mat(square_pix, (0, 0), (s1, s1), s1)
    # set_block_mat(square_pix, (0, s1), (s2, s1+s2), s2)
    # set_block_mat(square_pix, (0, s1+s2), (s3, s1+s2+s3), s3)
    # print(square_pix)

    edge_len = 154
    square_pix = make_mat(edge_len, edge_len, 0)
    s1 = 47
    s2 = 46
    s3 = 61
    set_block_mat(square_pix, (0, 0), (s1, s1), s1)
    set_block_mat(square_pix, (0, s1), (s2, s1+s2), s2)
    set_block_mat(square_pix, (0, s1+s2), (s3, s1+s2+s3), s3)
    edges = [2,5,9,11,16,17,19,21,22,24,26,30,31,33,35,36,41,50,52]
    # edges = [2,5,9,11,16,17,19,21,22,24,26,30,31,33,35,36,41,50,52, 47, 46, 61]
    per = PerfectSquare(square_pix, edges)

    # edge_len = 110
    # square_pix = make_mat(edge_len, edge_len, 0)
    # s1 = 60
    # s2 = 50
    # set_block_mat(square_pix, (0, 0), (s1, s1), s1)
    # set_block_mat(square_pix, (0, s1), (s2, s1+s2), s2)
    # edges = [2 ,3 ,4 ,6 ,7 ,8 ,12 ,13 ,14 ,15 ,16 ,17 ,18 ,21 ,22 ,23 ,24 ,26 ,27 ,28]
    # per = PerfectSquare(square_pix, edges)

    # edge_len = 4
    # square_pix = make_mat(edge_len, edge_len, 0)
    # edges = [1, 1, 1, 1, 1, 1, 1, 3]
    # per = PerfectSquare(square_pix, edges)

    # edge_len = 2
    # square_pix = make_mat(edge_len, edge_len, 0)
    # edges = [2]
    # per = PerfectSquare(square_pix, edges)

    # edge_len = 5
    # square_pix = make_mat(edge_len, edge_len, 0)
    # edges = [2, 2, 2, 3, 1, 1, 1, 1]
    # per = PerfectSquare(square_pix, edges)


if __name__ == "__main__":
    main()
